//package com.swordofferII.No076;
//
///**
// * @program: Solution
// * @description: 数组中的第 k 大的数字
// *      大顶堆
// * @author: Wang Zhihua
// * @date: 2022-12-09
// */
//public class Solution {
//    public int findKthLargest(int[] nums, int k) {
//        int len = nums.length;
//        int sonIdx = len;
//        while (sonIdx > 0) {
//
//        }
//    }
//
//    /**
//     * 更新子树，确保其为大顶堆
//     * @param nums 存储整个堆的数组
//     * @param rootIdx 当前子树的根节点对应数组的下标
//     * @param rootValue 根节点当前的值
//     * @param maxIdx 可以到达的最大的数组下标
//     *               （为了应对删除根节点后将其放到最后一个节点并对其不再做处理的情况）
//     */
//    private void updateTree(int[] nums, int rootIdx, int rootValue, int maxIdx) {
//        int leftSonIdx = getLeftSonIdx(rootIdx);
//        int rightSonIdx = getRightSonIdx(rootIdx);
//        if (leftSonIdx < maxIdx) {
//            if (nums[leftSonIdx] > rootValue) {
//                int tmp = nums[leftSonIdx];
//                nums[leftSonIdx] = rootValue;
//                nums[rootIdx] = tmp;
//                updateTree(nums, leftSonIdx, rootValue,maxIdx);
//            }
//        }
//        if (rightSonIdx < maxIdx) {
//            if (nums[rightSonIdx] > rootValue) {
//                int tmp = nums[rightSonIdx];
//                nums[rightSonIdx] = rootValue;
//                nums[rootIdx] = tmp;
//            }
//        }
//    }
//
//    // 这个方法针对堆数组从0开始的情况
//    private int getFatherIdx(int sonIdx) {
//        if ((sonIdx & 1) == 0) {
//            return (sonIdx >> 1) - 1;
//        } else {
//            return sonIdx >> 1;
//        }
//    }
//    // 这个方法针对堆数组从0开始的情况
//    private int getLeftSonIdx(int fatherIdx) {
//        return fatherIdx << 1 + 1;
//    }
//    // 这个方法针对堆数组从0开始的情况
//    private int getRightSonIdx(int fatherIdx) {
//        return fatherIdx << 1 + 2;
//    }
//}
